package 剑指Offer专项突破;

import java.util.Random;

/**
 * @Author zhang lei
 * @Date 2021-12-02 11:09
 */
public class Algo75 {
    public static void main(String[] args) {
//        System.out.println(findKthLargest(new int[]{4,5,6,1,2,3}, 3));
        int start = 1;
        int end = 5;

        for (int i = 0; i < 10; i++) {
            int random = (int) (Math.random()*(end-start)+start);
            System.out.println(random);
            new Random().nextInt();
        }

        //
        int n = 10;
        int[][] cost = new int[n][3];
        int[] r = new int[n];
        int[] g = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            r[i] = Math.min(g[i-1], b[i-1]) + cost[i][0];
            g[i] = Math.min(r[i-1], b[i-1]) + cost[i][1];
            b[i] = Math.min(r[i-1], g[i-1]) + cost[i][3];
        }

        int[][] dp = new int[n][2];
        //dp[i] 表示从0-i需要翻转的最少个数, 让0在1前面
        String s = "00110 ||  111000";

        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1]);
//            dp[i][1] = Math.min()
        }

    }


    /**
     * 快速排序
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0;
        int end = nums.length-1;
        int index = partition(nums, start, end);
        while (start<end) {
            if(index==target) {
                return nums[index];
            }else if(index<target){
                start = index+1;
            }else {
                end = index-1;
            }
            index = partition(nums, start, end);
        }

//        int result = quickSort(nums, 0, nums.length-1, k);
        return nums[index];
    }

    private static int quickSort(int[] nums, int start, int end, int k) {
        if(end>start) {
            int mid = partition(nums, start, end);
            if(mid >= k-1) {
                if(mid == 0 || mid == (nums.length-k-1)) {
                    return nums[mid+1];
                }
            }
            partition(nums, start, mid-1);
            partition(nums, mid+1, end);
        }
        return 0;
    }

    private static int partition(int[] nums, int start, int end) {
        int mid = new Random().nextInt(end-start+1)+start;
        int midNum = nums[mid];
        swap(nums, mid, end);

        int slow = start-1;
        int fast = start;
        while (fast<=end) {
            if(nums[fast]< midNum) {
                slow++;
                swap(nums, slow, fast);
            }
            fast++;
        }
        slow++;
        swap(nums, slow, end);
        return slow;
    }

    private static void swap(int[] nums, int i, int j) {
        if(i==j) {
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
